package com.itheima.leetcode.od.b.greedy;

import java.util.Arrays;

/**
 * (C卷,100分)- 数组组成的最小数字（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 给定一个整型数组，请从该数组中选择3个元素组成最小数字并输出
 * <p>
 * （如果数组长度小于3，则选择数组中所有元素来组成最小数字）。
 * <p>
 * 输入描述
 * <p>
 * 一行用半角逗号分割的字符串记录的整型数组，0 < 数组长度 <= 100，0 < 整数的取值范围 <= 10000。
 * <p>
 * 输出描述
 * <p>
 * 由3个元素组成的最小数字，如果数组长度小于3，则选择数组中所有元素来组成最小数字。
 * <p>
 * 用例
 * <p>
 * 输入	21,30,62,5,31
 * 输出	21305
 * 说明	数组长度超过3，需要选3个元素组成最小数字，21305由21,30,5三个元素组成的数字，为所有组合中最小的数字。
 * 输入	5,21
 * 输出	215
 * 说明	数组长度小于3， 选择所有元素来组成最小值，215为最小值。
 * <p>
 * 题目解析
 * <p>
 * 此题可以使用暴力法，求n个数取3个全排列，也就是O(n^3)的时间复杂度，但是题目提示0 < 数组长度 <= 100，这个数据规模很容易超时，因此我们应该想一想更优化的方法。
 * <p>
 * 我们知道Array.prototype.sort默认排序是按照Unicode值从小到大排的，因此对于只有两个数的情况，我们直接按照sort字典序升序，比如5,21，字典序升序后就是21,5，而215就是最小组合数。
 * <p>
 * 2023.02.03 这里直接对数组进行字典序升序，拼接后得到的组合数，不一定是最小的，比如数组 [3, 32, 321]，此时按照字典序升序后，还是 [3, 32, 321]，拼接出来为332321，而这显然不是最小的组合数，最小的组合数应该是321323。
 * <p>
 * 此处，得到最小组合数的正确排序规则应该是：请看下面博客解析华为OD机试 - 组合出合法最小数_伏城之外的博客-CSDN博客
 * <p>
 * 对于三个数及以上的数组，我们需要从中取出3个数，这个3个数，首先需要保证总长度最短，即保证组合数的位数最少，其值才能最小，因此我们需要将数组升序，这样小数在前，大数在后，我们只要取前三位即可，比如21,30,62,5,31升序为 5,21,30,31,62，取前3个，5,21,30然后进行sort默认排序，变为21，30，5，而21305就是最小值。
 */
public class MinUnion {
    public static void main(String[] args) {
        /*//处理输入
        Scanner in=new Scanner(System.in);
        String[] input_str = in.nextLine().split(",");*/

        String[] input_str = "21,30,62,5,31".split(",");
        if (input_str.length == 1) {
            System.out.println(input_str[0]);
        } else if (input_str.length == 2) {
            int num1 = Integer.parseInt(input_str[0] + input_str[1]);
            int num2 = Integer.parseInt(input_str[1] + input_str[0]);
            System.out.println(num1 < num2 ? num1 : num2);
            // 长度大于3才需要排序处理
        } else {
            Arrays.sort(input_str, (e1, e2) -> Integer.parseInt(e1) - Integer.parseInt(e2));
            String[] min_strs = Arrays.copyOf(input_str, 3);
            // 直接用string的compareTo函数即可
            Arrays.sort(min_strs, ((o1, o2) -> (o1 + o2).compareTo(o2 + o1)));
            String res = "";
            for (String s : min_strs) {
                res += s;
            }
            System.out.println(res);
        }
    }
}